package com.zdp.leetcodeMiddle;


/*
* 题目描述：
* 给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。​
设计一个算法计算出最大利润。
* 在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
示例:
输入: [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
* */
public class 最佳买卖股票时机含冷冻期_309 {

    /*
    * 解题思路： 利用 动态规划
    *  但这个显然有三种状态 ， 在第i天，会有三个状态：
    * 1. 手上持有股票  dp[i][0]
    * 2. 刚把股票卖掉，手上不持有股票，处于冷冻期 dp[i][1]
    * 3. 手上不持有股票，不处于冷冻期  dp[i][2]
    *
    * 得到 状态转移方程
    * dp[i+1][0] = max(dp[i][0],dp[i][2] + prices[i+1])
    *  i+1的手上持有股票的状态 是由 前一天持有股票，今天没买入 以及 前一天不持有股票，今天买入
    * dp[i+1][0] = dp[i][0] + prices[i+1]
    *  i+1天的 刚把股票卖掉的状态 是由 前一天持有股票 今天将股票卖掉得来的
    * dp[i+1][2] = max(dp[i][1],dp[i][2])
    *  i+1天的不持有股票，不处于冷冻期的状态，是由 前一天就不处于冷冻期 以及
    * 前一天处于冷冻期，今天不处于冷冻期
    * */
    public int maxProfit(int[] prices) {
        int length = prices.length;
        if(length == 0){
            return 0;
        }
        int[][] dp = new int[length][3];
        // 第一天持有股票 也就是第一天买入股票
        dp[0][0] = -prices[0];
        // 第一天处于冷冻期，就是 今天买入 今天抛
        dp[0][1] = 0;
        // 第一天不持股，不处于冷冻期 ---> 就是啥也没干
        dp[0][2] = 0;
        for(int i=1;i<length;i++){
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][2] - prices[i]);
            dp[i][1] = dp[i-1][0] + prices[i];
            dp[i][2] = Math.max(dp[i-1][2],dp[i-1][1]);
        }

        return Math.max(dp[length-1][1],dp[length-1][2]);
    }

    /*
    * 进行空间优化 ，第 i+1天 只与 第i天的状态有关
    * 可以不用数组 ，用三个变量即可
    * */
    public int maxProfit1(int[] prices){
        int length = prices.length;
        if(length == 0){
            return 0;
        }
        int f1 = -prices[0];
        int f2 = 0,f3 = 0;
        for(int i=1;i<length;i++){
            int newf1 = f1;
            int newf2 = f2;
            f1 = Math.max(f1,f3 - prices[i]);
            f2 = newf1 + prices[i];
            f3 = Math.max(f3,newf2);
        }

        return Math.max(f2,f3);
    }
}
